#include "sparce_table.hpp"
#include <cstdio>

sparce_table::sparce_table(int limx, int limy) {
	lx=0;ux=limx;
	ly=0;uy=limy;
	plx=ply=pux=puy=0;
}
sparce_table::sparce_table(int limx, int limy,int minx,int miny) {
	printf("New sparce table (%d,%d) (%d,%d)\n",minx,limx,miny,limy);
	lx=minx;ux=limx;
	ly=miny;uy=limy;
	plx=ply=pux=puy=0;
}

void sparce_table::clear() {
	if (plx) {plx->clear();delete plx;}
	if (ply) {ply->clear();delete ply;}
	if (pux) {pux->clear();delete pux;}
	if (puy) {puy->clear();delete puy;}
}

void sparce_table::touch() {
	printf("Touch: (%d,%d) (%d,%d)\n",lx,ux,ly,uy);
	if (!plx && lx!=ux) plx=new sparce_table((lx+ux)/2,uy,lx,ly);
	if (!ply && ly!=uy) ply=new sparce_table(ux,(ly+uy)/2,lx,ly);
	if (!pux && lx!=ux) pux=new sparce_table(ux,uy,(lx+ux)/2+1,ly);
	if (!puy && ly!=uy) puy=new sparce_table(ux,uy,lx,(ly+uy)/2+1);
}

void sparce_table::insdel(bool ins, entry obj, int x, int y, bool flag) {
	printf("Vertex: (%d,%d) (%d,%d)\n",lx,ux,ly,uy);
	if (lx<=x && x<=ux && ly<=y && y<=uy)
		if (ins)
			tree.ins(obj);
		else
			tree.del(obj);
	else return;
	if (ly!=uy && flag) {
		touch();
		ply->insdel(ins,obj,x,y,1);
		puy->insdel(ins,obj,x,y,1);
	}
	if (lx!=ux) {
		touch();
		plx->insdel(ins,obj,x,y,0);
		pux->insdel(ins,obj,x,y,0);
	}
}

void sparce_table::ins(entry obj) {
	int x=obj.time,y=obj.place;
	printf("Insertion of object started (%d,%d)\n",x,y);
	insdel(1,obj,x,y,1);
	printf("Insertion of object ended (%d,%d)\n",x,y);
}

void sparce_table::del(entry obj) {
	int x=obj.time,y=obj.place;
	insdel(0,obj,x,y,1);
}

void sparce_table::gen_list(list<entry> & l,int x1, int x2, int y1, int y2) {
	if (x2<lx || ux<x1 || y2<ly || uy<y2) return;
	if (tree.isempty()) {
		clear();
		return;
	}
	if (x1<=lx && ux<=x2) {
		if (y1<=ly && uy<=y2) {
			tree.gen_list(l);
		} else {
			touch();
			ply->gen_list(l,x1,x2,y1,y2);
			puy->gen_list(l,x1,x2,y1,y2);
		}
	} else {
		touch();
		plx->gen_list(l,x1,x2,y1,y2);
		pux->gen_list(l,x1,x2,y1,y2);
	}
}

list<entry> sparce_table::find(int lx, int ux, int ly, int uy) {
	list<entry> l;
	printf("Touch: (%d,%d) (%d,%d)\n",lx,ux,ly,uy);
	gen_list(l,lx,ux,ly,uy);
	return l;
}
